1. Field of the Invention
The present invention consists of building an apparatus for automated and secure generation of cryptographic algorithms using or not secret data. Said algorithms are generated by a secure module and have to be very different from each other.
2. Description of the Related Art
In the field of Pay TV, the card providers need to offer cryptographic protocols and algorithms different from one TV provider to another. Moreover some TV providers wish to change said cryptographic algorithm at predetermined period of time to increase the security of the system. One of the problems of the present invention is to offer secure cryptographic algorithm different from time to time or from one electronic system to another.
One other main problem to be solved is to achieve a good level of “algorithm secrecy”. In addition the generating method is designed in a way that it is able of systematically achieving algorithms that are secure against both algorithmic attacks on them and implementation (side-channel) attacks on an electronic system. Both these security properties are NOT properties of each individual algorithm but a non-trivial property of the generating apparatus. In fact, most of the known cryptographic and side-channel attacks will not work simply and precisely due to the algorithm secrecy that is achieved by the present invention. The central question of “algorithm secrecy” does not even make sense for each individual cryptographic algorithm, and can be defined as the impossibility for an attacker to gain some useful knowledge about one algorithm by observing another algorithm.
In order to secure access, electronic transactions and data, one has to use cryptographic protocols and (as a sub-component) secure cryptographic algorithms (for example encryption or digital signature algorithms). The security of a cryptographic algorithm cannot be seen: only the contrary can be seen, as many of them are broken every year by a new non-trivial mathematical or algorithmic method. It is even harder to securely implement such an algorithm in an electronic apparatus such as a smart card. For this reason many companies and governments have always kept the designs of crucial cryptographic algorithms secret. This is a common practice for algorithms used in GSM SIM cards, and in pay-TV smart cards. Shall the secrecy of these algorithms be breached, for example by reverse-engineering, the security of many systems does collapse, and cloned pirate cards do proliferate.
In order to achieve secure execution of cryptographic protections and secure storage of cryptographic keys, it is recommended to use secure tamper-resistant hardware security devices, such as smart cards.
A secure cryptographic algorithm implemented in a smart card brings new security concerns, which goes far beyond mathematical security. Now the algorithm is under physical control of an adversary and there are countless new possibilities of interaction by the physical means. With smart cards, the attackers gained the possibility of measurement and/or perturbation of the physical, electrical, magnetical and optical environment of the code execution process. All these are additional channels, which in some way interact with secret information concealed inside the device, are side-channels. They do leak information that may allow recovery of this secret information, or some fraudulent interaction, yet without recovering the secret data. For these reasons, today all serious vendors of secure hardware tokens such as smart cards, incorporate countless hardware and software counter-measures against various side-channel attacks (also called physical attacks).
The next step will be certainly to design cryptographic algorithms that have “per se” a good resistance against various side-channel attacks, and for which the cost of additional protections will be essentially the cost of implementing the functionality of the algorithm. This has not been done so far and nobody really knows how to achieve it. When this is done however, we will in some sense go back in the security level achieved: instead of a well known algorithm such as triple DES that have been under intense scrutiny of hundreds of researchers for 30 years, and that nobody has really cracked in a practical sense, we will have a new algorithm that may prove insecure a few years later, as it happens surprisingly frequently to new crypto algorithms.
In the present invention, we will avoid this flaw and design algorithms that will be as secure as a published and well-known algorithm such as AES (or another standard cryptographic algorithm). Unfortunately, using a public algorithm may make it again vulnerable to side-channel attacks. A secret algorithm is better.
In the present invention we will achieve, at the same time, security against side channel attacks and the possibility to be as secure as a renowned cryptographic standard. The invention consists in “embedding” a well-known cryptographic algorithm into a new algorithm in a specific way, such that certain security objectives are achieved. The main of these security objectives is to achieve a good level of “algorithm secrecy”. This goal is far from being obvious to achieve, as explained below, and according to opinions expressed by experts, it cannot be solved perfectly, yet it remains an important industrial issue that has to be addressed (for example in pay-TV or telecoms).
The problem of algorithm secrecy should be seen at three different levels:
1) In mathematics one cannot invent a “secret algorithm”. Any algorithm with unknown bits of specification is secret, and has some entropy. At this level there is nothing non-trivial to invent.
2) In cryptology, one allows the attacker to interact with the algorithm, and the notion of secrecy of an algorithm becomes meaningful. One has to study the complex question of: to what extent the algorithm is indeed secret, since some partial information is available. Some algorithms will be secret; some can be partially or totally recovered by a skilled attacker. In many cases, the algorithm will be recovered by a non-trivial mathematical method, and it is not known how to prove that for some algorithm such a method does not exist. The expired Rivest-Shamir-Adleman US patent on RSA cryptosystem is also a patent on encryption algorithm secrecy. Indeed, it was for some time, about the only method known to publish the encryption algorithm and yet to keep the decryption algorithm secret. To this day very few methods to achieve this goal (i.e. achieving public key encryption) are known, and it is a highly non-trivial task to invent a new one. This demonstrates that algorithm secrecy is a highly difficult goal to achieve.
3) In embedded cryptology, for example when a cryptographic algorithm is implemented in a smart card, it is again a new world, even more constrained. As security is, the algorithm secrecy is even harder to achieve here. This is because; it has to hold not only when the adversary has access to the functionality of the algorithm (cf. point 2.) but when the side-channels are available.
At present time some smart cards use algorithms that are secret (for example for GSM operators). However to see to what extent they are indeed secret, this question has never been studied in the literature and no solutions to address this problem have been proposed.
An aim of this invention is to offer versions of a cryptographic algorithm with a good level of algorithm secrecy (how good will be explained later) and a good cryptographic security.